#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 11  // 散列表大小

typedef struct HashTable {
    int* table;         // 哈希表
    int* deleted;       // 标记已删除的槽位
} HashTable;

// 创建哈希表
HashTable* createHashTable() {
    HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
    ht->table = (int*)malloc(TABLE_SIZE * sizeof(int));
    ht->deleted = (int*)malloc(TABLE_SIZE * sizeof(int));
    
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->table[i] = -1;     // 初始化为 -1，表示槽位为空
        ht->deleted[i] = 0;    // 初始化为 0，表示未删除
    }
    
    return ht;
}

// 哈希函数
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// 插入元素
void insert(HashTable* ht, int key) {
    int index = hashFunction(key);
    int originalIndex = index;  // 保存原始索引以检测循环

    while (ht->table[index] != -1 && ht->deleted[index] == 0) {//地址冲突
        // 找到下一个可用槽位
        index = (index + 1) % TABLE_SIZE; //开放地址法解决冲突， 1 为增量序列的实例

        // 如果回到原始索引，表示表已满
        if (index == originalIndex) {
            printf("Hash table is full!\n");
            return;
        }
    }

    ht->table[index] = key;  // 插入元素
    ht->deleted[index] = 0;  // 标记为未删除
}

// 查找元素
int search(HashTable* ht, int key) {
    int index = hashFunction(key);
    int originalIndex = index;

    while (ht->table[index] != -1) {
        if (ht->deleted[index] == 0 && ht->table[index] == key) {
            return index;  // 找到元素
        }
        index = (index + 1) % TABLE_SIZE;  // 继续探测
        if (index == originalIndex) {
            break;  // 返回到起始位置，未找到
        }
    }
    
    return -1;  // 元素未找到
}

// 删除元素
void delete(HashTable* ht, int key) {
    int index = search(ht, key);
    if (index != -1) {
        ht->deleted[index] = 1;  // 标记为已删除
        printf("Deleted key %d from index %d\n", key, index);
    } else {
        printf("Key %d not found for deletion\n", key);
    }
}

// 打印哈希表
void printHashTable(HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (ht->table[i] != -1) {
            printf("Index %d: %d%s\n", i, ht->table[i], ht->deleted[i] ? " (deleted)" : "");
        } else {
            printf("Index %d: (empty)\n", i);
        }
    }
}

// 主函数
int main() {
    HashTable* ht = createHashTable();

    insert(ht, 10);
    insert(ht, 22);
    insert(ht, 31);
    insert(ht, 4);
    insert(ht, 15);
    insert(ht, 28);
    insert(ht, 17);
    insert(ht, 88);
    insert(ht, 59);

    printf("Hash table after inserts:\n");
    printHashTable(ht);

    printf("Searching for key 22: Found at index %d\n", search(ht, 22));
    printf("Searching for key 100: Found at index %d\n", search(ht, 100));

    delete(ht, 22);
    printf("Hash table after deleting 22:\n");
    printHashTable(ht);

    delete(ht, 100);  // 尝试删除一个不存在的键

    // 释放内存
    free(ht->table);
    free(ht->deleted);
    free(ht);
    
    return 0;
}
